\documentclass{article} 

\usepackage{amsfonts} 
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{graphics}
\usepackage{epsfig}
\usepackage{mathsymb}
\usepackage{algorithmic}

\newtheorem{definition}{{\bf Definition}}
\newtheorem{theorem}{{\bf Theorem}}
\newtheorem{lemma}{{\bf Lemma}}
\newtheorem{corollary}{{\bf Corollary}}
\newtheorem{observation}{{\bf Observation}}


\newcommand{\commentv}[1]{{\bf **Victor: #1**}}

\newcommand{\supp}{\operatorname{supp}} 

\title{Equilibria in Simultaneous Auctions via Fictitious Play and its
  Properties}

\begin{document}
\maketitle
\begin{abstract}
%
%----- VERBAL VERSION
%
In this paper we provide an analytical and empirical solution to a
complete class of simultaneously-held auctions, as opposed to
classically studied individual specialised cases. More specifically we
study the complete range of simultaneously-held auctions from
substututes to complements by applying the formalism of games with a
(virtual) continuum of anonymous players (CAPs). By extending the Fictitious
Play (FP) algorithm to CAPs, we are able to quickly generate an
equilibrium solution to any auction within the studied
range. Furthermore, along the empirical results we present, the analysis
of the algorithm's properties enabled us to create an alternative
analytical formulation for the equilibrium of the studied range of
simultaneous auctions. Among other results, this analytical view
enables a complete structural classification of the aforementioned
equilibria. Althgouh we show that the practical applicability of our method is
much greater, as an illustration we provide the analysis of a
2-bidder, 2-auction, 2-bids simultanious auctions were the equilibria
are parameterised by the preference relations. To the best of our
knowledge, this is the first time such an exhaustive analysis became
possible using a single technique. We further corroborate our results
by demonstrating that the theoretical analysis and our original FP
generated solution coinside.

 ---------------- ITEMISED VERSION -- PLEASE COMPARE (WITHOUT PREJUDICE :) )

In this paper, we:
\begin{itemize}
\item analyse equilibrium strategies for agents participating in
  multiple, simultaneously-held sealed-bid auctions with discrete bids
\item do so theoretically for a limited setting (2 bidders, 2
  auctions, 2 bid levels per auction), but for various preference
  relations (substitutes, complements, and inbetween)
\item show how this analysis can be extended to other cases, but
  becomes intractable very quickly
\item introduce computational algorithm based on fictitious play (FP)
\item analyse the simple setting using FP
\item show that theoretical results correspond to FP results
\item analyse more general settings using FP
\item show that FP converges, i.e. finds an equilibrium
\item compare different auction formats (first and second price)
\item discuss the application of the algorithm as well as theoretical
  approach to more general setting, i.e. any Bayesian game where
  players have quasi-linear utility functions and finite possible
  actions
\end{itemize}

\end{abstract}

\section{Introduction:Motivation}
\begin{itemize}
\item our analysis applies to settings where bids need to be placed
  before outcome of other auctions is known
\item applies to many settings, not just auctions, e.g. job
  applications, procurement contracts
\item simultaneous auctions effective way of quickly selling multiple
  items, e.g. computational resources
\item similar mechanism often used for e.g. spectrum licence auctions,
  although often this consists of multiple rounds. However, having
  multiple rounds is more susceptible to tacit collusion (famous
  account where bids were used as signalling devices).
\item lots of previous work on simultaneous sealed-bid auctions, both
  from OR and MAS literature, but equilibrium has largely remainded
  open problem, therefore proper evaluation of mechanism has not been
  possible:
\begin{itemize}
\item work by Rosenthal, e.g. \cite{szentes2003three} et al assumes
  essentially that players have the same preferences for the items
  (i.e. there are no unknown types)
\item work by Fatima et al, e.g. \cite{fatima2008bidding} assumes that
  bidders need to choose one of the auctions. However, Gerding et al
  have shown in \cite{ecs16075} that this is not optimal even for
  perfect substitutes (i.e. if everyone chooses only 1 of the
  auctions, then it is a best response under fairly general conditions
  to bid sctrictly positive in all auctions)
\item related is the work on competing auctions, but there the
  emphasis is on the seller or auction mechanism, and although in
  doing so they consider the bidder strategies as well, they similarly
  assume that bidders will only go to one of the auctions.
\item a number of papers, such as \cite{ecs16075} and \cite{ecs12600}
  allow bidders to bid in multiple auctions but only consider decision
  theoretic settings, not equilibria
\item equilibria are analysed in \cite{krishna1996simultaneous}, but
  that's only for the case of complementary valuations and continuous
  bids. Our preference structure is more general and we consider
  discrete bids.
\item closest is our own previous work in \cite{ecs17271}, which also
  used FP to analyse simultaneous auctions, but only considers perfect
  substitutes. We significantly extend this work by adding theoretical
  analysis, consider more general preferences, provide extensive
  experiments and analysis of the strategies, and compare first and
  second price auctions.
\end{itemize}
\end{itemize}

\section{Notation}
Unless specified otherwise, our notation will adhire to the following rules:
\begin{itemize}
\item Vectors and vector spaces will be denoted by a
  bold face letter, e.g $\mathbf{\alpha}\in\mathbf{R}^n$, same is true
  for elements of finite subsets of vector spaces,
  e.g. $\mathbf{b}\in\mathbf{B}$, where the latter is the set of all
  multi-bid vectors.
\item An element of a vector will be denoted by a subscript using the
  same letter as the vector itself, but in normal font. E.g. for
  $\mathbf{b}=(b_1,...,b_n)$. Given a set of indexes
  $\eta\subseteq[1:n]$ a sub-fector will be denoted by a negative
  subscript, e.g. $(b_{i_1},...,b_{i_l})=\mathbf{b}_{-\eta}$, where
  $\eta=[1:n]\setminus\{i_1,...,i_l\}$.
\item Families of complex objects, such as functions, which do not
  necessarily comprise a vector space will be denoted by an italic
  letter, e.g. $\mathcal{F}=\{h:V\rightarrow A|h(v_0)=1\}$.
\end{itemize}

%% \section*{Model (Victor)} We consider games of incomplete
%% information with continuous type spaces and finite action
%% spaces. We follow the independent private value model with
%% symmetric players. Each player draws his type independently from a
%% commonly known atomless distribution $F$ over the continuous set of
%% possible types $\Theta$. An identical finite set of actions $A$ is
%% available to each player. Utility of player $i$ depends only on his
%% type, his action, and actions of the other players $u: \Theta
%% \times A^n \to \R$. Formally, the game is a tuple $\Gamma = \langle
%% n,A,u,\Theta,F \rangle$.

%% Pure strategy of a player is a function that maps his type to an
%% action $s:\Theta \to A$. Let a random variable $T$ denote the types
%% of the other players. The expected utility of a player with type
%% $\theta$ when playing action $a$ is $E_{T}[u(\theta,a,s(T))]$ or
%% equivalently, $E_{s(T)}[u(\theta,a,s(T))]$. For computational
%% reasons, we prefer the latter as there is a finite number of action
%% profiles $s(T)$ while there is a continuum of type profiles $T$.

%% A symmetric pure strategy Bayesian Nash equilibrium (BNE) of the
%% game $\Gamma$ is a strategy that maximizes the expected utility for
%% each of player's types when the other players follow this
%% strategy.  \begin{definition} The strategy $s$ is a symmetric pure
%% strategy BNE if \begin{align} & E_{s(T)}[u(\theta,s(\theta),s(T))]
%% \ge E_{s(T)}[u(\theta,a,s(T))] \quad \forall\ \theta \in
%% \Theta,\ a\in A \end{align} \end{definition}

%% A symmetric pure strategy BNE is guaranteed to exist in the class
%% of games we described~\cite{mas-colell_84}.

\section{General model and auction's instantiation}
In this paper we concern ourselves with a highly symmetric setup of
games with private information with common spaces of continuous type
and finite action. In addition we will also assume double
anonymity. That is a player's utility depends only on the set of
opponent actions and the player's type\footnote{Anonymity refers to
  the independency of the utility function on identity of
  players. Most common in the literature is the independency from the
  identity of opponents, where the utility depends only on the
  unordered, hence anonymous, set of actions selected by the
  opponents. Nevertheless, it is possible that, all other things
  equal, the utility may differ from player to player. However, we
  assume that this is not the case either.}. Such games are well
represented by auctions, and we will employ our model to provide a
general computational and analysis techniques for simultaneous
auctions. More specifically, we will be interested in ways to obtain
and characterise symmetric equilibria of the aforementioned games. In
order to do so, we first develop a variation of the standard 
model of games with private information~\cite{radner_rosenthal_82} 
that allows us to concentrate specifically on symmetric equilibria,
and capitlise on the findings of Mas-Colell~\cite{mas-colell_84} and
other similar works~\cite{schmeidler_73,khan_sun_2002}. To give a
more intuitive insight into the operation of our model, we
instantiate it for simultaneous auctions. We show that the model
allows us to represent a complete range of auctions from complete
substitues to full complimentarities, including non-trivial disposal
costs.

%% In this section we will present a variation on the model of games with
%% private information, also known as games with a continuum of anonymous
%% players~\cite{schmeidler_73,radner_rosenthal_82,mas-colell_84,khan_sun_2002}. Specifically,
%% we will provide a model for a game between a finite set of player with
%% private type sampled from a common continuous distribution, and concentrate on
%% the case where the set of actions available to the players is finite
%% as well. Formally the notation will be a combination of the notation
%% used by Mas-Colell~\cite{mas-colell_84} and that of Radner and
%% Rosenthal~\cite{radner_rosenthal_82}. This is done to expose the
%% internal structure of the problems we tackle, while remaining closer
%% to the more commonly used strategy oriented representation of an
%% equilibrium. To demonstrate how our model is used, we will instantiate
%% it for the case of simultaneous auctions. Furthermore, we will show
%% that by modifying model parameters, but never the model structure, we
%% are able to represent the complete range of simultaneous auctions:
%% from substitutes to compliments, including free and non-free disposal.

\subsection{Model Composition for Symmetric Games}\label{bne_in_caps}
We will begin by noting the standard portions of the model, namely the tuple 
$<I,A,V,\mu>$, where:
\begin{itemize}
\item $I$ is the finite set of players, $|I|=n$
\item $A$ is the common, finite set of actions available to players
\begin{itemize}
\item The space of distributions over $A$ is then a $|A|$-simplex, $\Delta(A)$. 
\end{itemize}
\item $V$ is the common continuous type space
\item $\mu$ is a continuous distribution over $V$
\begin{itemize}
\item Individual player types are sampled i.i.d. prior to action
  selection, and remain fixed.
\end{itemize}
\end{itemize}

What remains to complete this tuple to a complete model of a game is
to define a utility function. In non-anonymous games $n$ utility
functions of the following shape are needed $\xi_i:V\times
A\times\Delta(A)^{n-1}\rightarrow\mathbf{R}$. These are subjective
functions functions, and $\xi_i(v,a,\mathbf{m}_{-i})$ is the utility
of player $i\in I$ with private type $v\in V$ that applied action
$a\in A$ and believs that its opponents will apply actions with
probability distribution $\mathbf{m}_{-i}$. However, we assumed
symmetry and specifically independence from the player's identity,
that is $\xi_i=\xi$ for all $i\in I$, where $\xi$ is a function of
the appropriate form. As we will show, this is sufficient to establish
the existense of a symmetric Bayes-Nash equilibrium. We then further
utilise the game symmetry, specifically the anonymity of opponent
actions, which enables us to focus on utility functions of the form
$u:V\times A\times\Delta(A)\rightarrow\mathbf{R}$. To achieve this we
first have to look at the space of possible strategies available to a
player. The simplest form a strategy can take is a function
$h:V\rightarrow A$, also known as a pure strategy. In turn, a complete (pure)
strategy profile, that prescribes a strategy to each of the players,
is a vector function $\mathbf{h}=(h_i)_{i\in I}$ formed by individual
strategies of players. As a consequence, a pure strategy Bayes-Nash
equilibrium is defined as follows.

\begin{definition} 
Given a game $<I,A,V,\mu,\xi>$.  Denote
$m_i(\cdot)=\mu(h_i^{-1}(\cdot))$, then a complete (pure) strategy
profile $\mathbf{h}=(h_1,...,h_n)$ is a Bayes-Nash Equilibrium (BNE)
$\iff \forall i\in I , \forall v_i\in V,
\xi(v_i,h_i(v_i),\mathbf{m}_{-i})=\max\limits_{a_i\in
  A}\xi(v_i,a_i,\mathbf{m}_{-i})$. That is, for any player $i\in I$,
the pure strategy $h_i$ always dictates the best choice of action for
any possible assignment of private type.
\end{definition}

It is necessary to remark upon the interpretation of the chosen shape
for the uility function $\xi$. Most commonly $\xi$ would be seen as
the expected utility given the beliefs $\mathbf{m}_{-i}$ dictated by
the opponent strategies. In other words, it is assumed that only
actions actually applied yield utility descrbied by a function
$\tilde{\xi}:V\times A^n\rightarrow\mathbf{R}$, and
$\xi(v_i,a_i,\mathbf{m}_{-i})=\mathcal{E}_{\mathbf{m}_{-i}}\tilde{\xi}=
\mathcal{E}_{T^{n-1}}\tilde{\xi}(v_i,a_i,\mathbf{h}_{-i}(v_{-i}))$. However,
this is not necessarily so, and the shape of the utility function
$\xi$ can capture a much wider variety of scenarios, than the simple
expectation. For instance, we can capture scenarios, where the utility
depends on the amount of information a player has about its
opponents. As an example, consider reducing the utility if the
opponent actions are less predictable. That is we can model risk
assesment by the entropy of opponent actions, and model risk aversion
by the function $\xi(v_i,a_i,\mathbf{m}_{-i})=
\mathcal{E}_{\mathbf{m}_{-i}}\tilde{\xi}-\sum\limits_{j\neq i\in
  I}H(m_j)$, where $H(\cdot)$ is the discrete distribution
entropy\cite{cover_thomas_book}.

Now, among all possible BNE's for the games we are interested in, of a
particular interst are the {\em symmetric} BNEs, so that for all $i\in
I$ $h_i=h$ for some $h:V\rightarrow A$. The following theorem provides
the conditions for its existence.

\begin{theorem}[(adapted from ~\cite{mas-colell_84})]\label{sym_cne_theorem}
Given a game $<I,A,V,\mu,\xi>$. If $A$ is finite, $\mu$ is nonatomic,
and functions $\xi(v,\cdot,\cdot)$ are continuous for all $v\in V$,
then a pure symmetric equilibrium exists. That is, there is a function
$h:V\rightarrow A$, so that $\mathbf{h}=(h_1,...,h_n)$ with $h_i=h$
for all $i\in I$ is a BNE.
\end{theorem}
Althouh the exact formalism is different, it is almost straight
forward to utilise the proof of Theorem 2 from Mas-Colell's work on
non-atomic games~\cite{mas-colell_84}. We quote it here with minor
modifications to allow for the discrepancy in formalisms. 
\begin{proof}
Let $u(v,a,m)=\xi(v,a,\tilde{m})$, where $\tilde{m}=(\tilde{m}_j)$ and
$\tilde{m}_j=m$ for all $j$. 

\begin{quote}[begin quote from ~\cite{mas-colell_84}]

Denote $A=\{a_1,...,a_k\}$, and identify
$\mathcal{M}$ with the $k-1$ simplex: $\mathcal{M}=\Delta(A)$. Let
$\mathcal{F}=\supp \mu$ and define the correspondence
$\Phi:\mathcal{F}\times\mathcal{M}\rightarrow\mathbf{R}^k$ by
$$
\Phi(v,m)=\{e_j|u(v,a_j,m)\geq u(v,A,m)\}.
$$

$\Phi$ is non-empty valued and upper hemicontinuous. Define $\Phi:\mathcal{M}\rightarrow\mathcal{M}$ as follows:
$$
\Phi(m)=\int\phi(v,m)d\mu(v)
$$ 

Since $\mu$ is atomless, $\phi$ is non-empty convex valued and upper
hemicontinuous. By the Kakutani Fixed Point Theorem there is
$\tilde{m}\in\Phi(\tilde{m})$. That is there is a measurable function
$h:\mathcal{F}\rightarrow A$ such that $u(v,h(v),\tilde{m})\geq
u(v,h(v),\tilde{m})$ for $\mu$-a.e. $v\in \mathcal{F}$ and
$\tilde{m}=\mu\circ h^{-1}$.

[end quote]
\end{quote}

Expanding $h$ to the entire space $V$, and conforming to our
formalism, this provides us with the symmetric pure strategy
equilibrium $\mathbf{h}=(h_i)$ with $h_i=h$.

\end{proof}

Since in this paper we will be interested in symmetric equilibria, we
will assume that the conditions of Theorem~\ref{sym_cne_theorem}
hold. As an outcome of these assumptions and the structure of the
proof, we can replace the original shape of the utility function by
the shape\footnote{Although the number of players is no longer a part
  of the argument structure of the utility function, it will continue
  to implicitly influence the function's curvature. An example of this
  can be seen in our instantiation of the model for simultaneous
  auctions in subsection~\ref{sim_auc_inst}.}
$u(v,a,m)=\xi(v,a,\bar{\mathbf{m}})$ with
$\bar{\mathbf{m}}=\underbrace{(m,...,m)}_{{\tiny (n-1)\ {\tiny
      times}}}$, so that a game is described by the tuple
$<I,A,V,\mu,u>$, where :
\begin{itemize}
%\item $I$ is the finite set of players, $|I|=n$
%\item $A$ is the finite space of actions available to players
%\item $V$ is the continuous type space
%\item $\mu$ is a continuous distibution over $V$
\item $I$, $A$, $V$ and $\mu$ are as before
\item $u:V\times A\times\Delta(A)\rightarrow\mathbf{R}$, where
  $u(v,a,m)$ is the subjective utility of a player with type $v\in V$,
  if it applies action $a\in A$ and the distribution of actions that
  the player's opponent can appply is given by the the distribution
  $m\in\Delta(A)$.
\begin{itemize}
\item We will naturally denote by subscripts projections of $u$,
  for example $u_v(a,m)=u(v,a,m)$ and
  $u_{a,m}(v)=u(v,a,m)$.
\item It is assumed that $u_v$ is continuous for all $v\in V$.
\end{itemize}
\end{itemize}

Now, formally it is possible to expand the space of applicable
strategy profiles by considering mappings of the form
$\tilde{h}:V\rightarrow\Delta(A)$, where a player with type $v\in V$
{\em samples} its action from the distribution $\tilde{h}(v)$. This,
however, will not improve the set of attainable utilities, that is any
mixed profile is weakly dominated by some pure strategy
profile~\cite{radner_rosenthal_82}. This provides us with the
justification to concentrate on the pure strategy profiles and
equilibria, and the above model. 

\subsection{Simultaneous Auctions Instantiation}\label{sim_auc_inst}
To examplify the strength of the model we use, consider modelling the
following auctioning scenario. A finite number of $K$ auctions is held
simultaneously, and a group $I$ of bidders, $|I|=n$, step forward to
place bids in these auctions. Each bidder holds a private value, but
we may assume that it was i.i.d sampled from the interval $[0,1]$ due
to some continuous distribution $\mu$ over it. Furthermore, given that
the real money has discrete and exhaustable nature, we can assume that
each auction has an associated finite set of bids $B_k$ from which the
bidders can choose which one they would like to place. Denote
$\mathbf{B}=\prod\limits_{k\in K}B_k$ the space of all complete bids,
so that $\mathbf{b}=(b_1,...,b_{|K|})$ prescribes a bid for each
auction. Then a pure strategy for a bidder takes form of a function
$h:V\rightarrow\mathbf{B}$, and we will be interested to find such
function that forms the basis of a symmetric equilibrium. That is, if
all players adopt $h$ as their strategy, no player will have an
incentive to vary it. Moreover, the symmetry assumptions holds, and
the utility of a player is dictated by his value of auctioned items,
its bid and the bids of opposing bidders\footnote{In fact, it is quite common
to define an intermediary function $\tilde{\xi}:V\times
A^n\rightarrow\mathbf{R}$ that determines the utility of a player
under specific bids placed.}. The
resulting model is described by a tuple $<I,A,V,\mu,u>$:
\begin{itemize}
\item The action space $A=\mathbf{B}=\prod\limits_{k\in K}B_k$
\begin{itemize}
\item Naturally $\Delta(\mathbf{B})$ the simplex of all
  discrete distributions over the space of complete bids.
\end{itemize}
\item The type space $V=[0,1]$ and $\mu$ are taken as is.
\item The utility function has the shape $u:V\times\mathbf{B}\times 
  \Delta(\mathbf{B})\rightarrow\mathbf{R}$, where $u(v,\mathbf{b},m)$
  determines the utility for a bidder with private type $v\in V$, if
  he places a complete bid $\mathbf{b}=(b_1,..,b_{|K|})\in\mathbf{B}$
  (i.e. he places bid $b_k$ in the auction $k\in K$), while the
  probability of counterbids is given by $m\in\Delta(\mathcal{B})$. It
  is assumed that $u$ correctly represents the fact that $m$ will be
  perused independently by $n-1$ opponents.
\end{itemize}

Notice that this model does not limit itself to any specific secondary
auction property, such as the choice of second or first price
payements, the choice of cobinatorial or complimentary or substitute
utilisation of items, or the choice of tie breaking rule. Such
secondary properties may be needed for the calculation of a specific
equilibrium, but are comlpetely superfluous for obtaining analytical
results (see Section~\ref{analytic_results}) or the construction of a
computational algorithm (see
Section~\ref{empirical_results}). Detailed payment and tie-breaking
assumptions are also unnecessary to obtain equilibrium existance,
since Theorem~\ref{sym_cne_theorem} allows us to formulate the
following Corollary.

\begin{corollary}[BNE of auctions]\label{pure_sym_bne}
Assume that an auctions setting is given with a continuous
distribution, $\mu$, over private types, $V$, and a finite set of
bids, $\mathbf{B}$, available to each player. If the utility function
of a bidder is continuous in the bid placed and the opponent bid
distribution, then there exists a pure symmetric Bayes-Nash
Equilibrium (BNE) strategy $h:V\rightarrow\mathbf{B}$.
\end{corollary}

However, in spite of general capabilities of our modelling approach in
describing auction scenarios, in this paper we will pay particular
attention to the $u$ function of the form
$u(v,\mathbf{b},m)=\sum\limits_{\eta\subseteq
  K}P_B(\mathbf{b},\eta)\phi_\eta(v)-c(\mathbf{b})$, where:
\begin{itemize}
\item $P_B(\mathbf{b},\eta)$ is the probability that placing bids
  $\mathbf{b}$ will result in winning exactly the set $\eta$ of
  auctions, and in Appendix~\ref{???} we show how this distribution is
  obtained from the distribution of opponent bids
  $m\in\Delta(\mathbf{B})$.
\item $\phi_\eta(v)$ is the utility procured by winning exactly $\eta$
  auctions as a function of private value
\item $c(\mathbf{b})$ is the expected utility lost (payed) incurred as
  a function of placed bids $\mathbf{b}$
\end{itemize}

We will further simplify this structure by assuming that
$\phi_\eta(v)=\alpha_\eta*v$ , where $\{\alpha_\eta\}_{\eta\subseteq
  K}$ is a commonly known set of preferences that determine the
complimentarity structure. Notice that the resulting expression for
the utility is $u(v,\mathbf{b},m)=\sum\limits_{\eta\subseteq
  K}P_B(\mathbf{b},\eta)*\alpha_\eta*v-c(\mathbf{b})$, and adjusting
$\alpha_\eta$ enables us to span the full spectrum from pure
compliments to pure substitues. 

As a running example, consider the 2x2x2 case. That is we are
simultaneously running two auctions, $K=\{k_1,k_2\}$, there are two
bidders $I=\{$Primo,Secondo$\}$, and there are only two bidding levels
(``all or nothing'') available in each auction. Assume, without
limitation of generality, that Secondo has fixed it's policy
$h_2:V\rightarrow\mathbf{B}$. Then Primo will have to outbid an
opponent bid $\mathbf{b}\in\mathbf{B}$ with probability
$m(\mathbf{b})=\mu(h_2^{-1}(\mathbf{b}))$. Denote $\eta_1$ and
$\eta_2$ the events that Primo wins exclusively auction $k_1$ and
$k_2$ respectively, and by $\eta_1\cap\eta_2$ the case where both
auctions are won. Then Primo's utility is:
\begin{eqnarray*}
u(\mathbf{b},v_1,P_B)&=&P_B(\mathbf{b},\eta_1)*\alpha_{\eta_1}*v_1+\\
&&P_B(\mathbf{b},\eta_2)*\alpha_{\eta_2}*v_1+\\
&&P_B(\mathbf{b},\eta_1\cap\eta_2)*\alpha_{\eta_1\cap\eta_2}*v-c(\mathbf{b}),
\end{eqnarray*}
and it becomes clearer how $\alpha_\eta$ can produce various
complimentarity structures. Consider the following examples:
\begin{itemize}
\item Setting $\alpha_{\eta_1}=\alpha_{\eta_2}=\alpha_{\eta_1\cap\eta_2}=1$ produces
the pure substitues case. That is, even if the agent wins both auctions his
utility from the won objects corresponds to the agent's private
value. As would happen if two TV sets, where only one is needed.
\item The case where $\alpha_{\eta_1}=\alpha_{\eta_2}=0$ and
  $\alpha_{\eta_1\cap\eta_2}=1$ produces pure compliments: only if
  both auctioned items are won, the agent receives a positive utility
  signal. As would be the case where the left and the right door flaps
  are sold separately.
\item Setting
  $\alpha_{\eta_1\cap\eta_2}=\alpha_{\eta_1}+\alpha_{\eta_2}$ produces
  independent auctions with additive utility gained from their
  items. As would happen in auctioning separately two barrels of oil.
\item Finally, setting $\alpha_{\eta_2}=2*\alpha_{\eta_1}$ and
  $2*\alpha_{\eta_1}\leq\alpha_{\eta_1\cap\eta_2}\leq
  3*\alpha_{\eta_1}$ produces a structure where item auction in $k_2$
  is twice as profitable as that of $k_1$, but the items can interfere
  with each other reducing the utility if both are won. As would
  happen if two distict prized orchids are obtained --
  cross-polination needs to be prevented to maintain the species.
\end{itemize}

To complete the description of our example auction setup, it is
commonly accepted as necessary to describe how tie breaking occurs,
and how the cost corresponds to the bid placed. However, in our model
these issues are abstracted by the probabilities
$P(\mathbf{b}\in\mathbf{B},\eta\subset K)$ and the expected cost
$c(\mathbf{b})$. Furthermore, in general, our analytical and empirical
techniques do not depend on a particular instantiation of the tie
breaking nor cost function. Nevertheless, to ease the presentation we
will adopt the following assumptions:
\begin{itemize}
\item The tie breaking is fair, that is if $n\subset N$ bidders place
  the same bid $b_k\in B_k$ on auction $k\in K$, then each bidder will
  have the probability $\frac{1}{|n|}$ to win the
  item. $P(\mathbf{b}\in\mathbf{B},\eta\subset K)$ is calculated
  accordingly (see Appendix~\ref{cost_win_numeric} for the 2x2x2 case).
\item The auctions are second price, that is the cost to agent $i\in
  N$ of winning an auction $k\in K$ by placing a bid $b^i_k\in B_k$ is
  $\max\{b^j_k|j\neq i\}$, where $b^j_k$ denotes the bid placed by
  agent $j\in N$ in auction $k\in K$. $c(\mathbf{b})$ is calculated
  accordingly(see Appendix~\ref{cost_win_numeric} for the 2x2x2 case).
\end{itemize}

In Appendix~\ref{cost_win_numeric}, we show how these assumptions
enter our 2x2x2 example with an additional assumption that
$B_k=\{low,high\}=\{0,1\}$. Interestingly, the calculation of the best
response strategy does not principally depend on these details
either. Since the set of possible bids is finite, the exact structure
of $P(\mathbf{b},\eta)$ and $c(\mathbf{b})$ places no restriction on
the ability to optimize $u(\mathbf{b},v,P_B)$. In fact, the
calculation of the best possible utility, and its corresponding
strategy (see Section~\ref{br_calc}), can lead to structural
classification of the possible equilibria, and ultimately results in
the analytical approach that we present in
Section~\ref{analytic_results}. 

\section{Best Response Structure}\label{br_calc}

Under the assumptions of the Theorem~\ref{sym_cne_theorem}, the
symmetry of the utility function with respect to player's identity
enables us to calculate the best response utility with respect to a given
distribution of opponent actions, and it's corresponding strategy. In
this section we show how this can be done, and then use the best
response calculation to create a version of the Fictitious Play (FP)
algorithm targeted at computing the symmetric equilibria.

%\section{CAPs FP}
%In this section we show that a computational algorithm for the
%discovery of Nash-type equilibrium, namely Fictitious Play (FP)
%algorithm, can be adopted to work with CAPs formulation.

%\subsection{Best Response}
As was mentioned before we are concentrating on the strategy space of
the shape $h:V\rightarrow A$. Let's assume that all players, but one,
have fixed their policy, and therefore each generates action
distribution $m\in\Delta(A)$. For the remaining player we need to
calculate the best utility it can gain under these circumstances, and
the action that produces this utility for each of it's possible
types. In other words we need to calculate the following function:
$$h_{BR}(v)=\arg\max\limits_{\mathbf{a}\in A}u(v,a,m)$$

The utility of the best best response is naturally an upper envelope
of a finite set of function $\{u_{a,m}(\cdot)\}$, as depicted in
Figure~\ref{plc_br_shape}.
\begin{figure}[ht]
\centerline{\psfig{file=img/lin_rep.eps,width=4cm}}
\caption{\label{plc_br_shape}Piece-wise linear shape of the best
  response utility}
\end{figure}

The envelope's structure gives rise to an alternative way to capture
the best response function $h_{BR}$. This method aggregates together
all player types where a particular function $u_{a,m}$ matches the
upper evelope, and associates the action $a$ with this set of
types. It is easy to see that this build a correspondence equivalent
to that of $h_{BR}$. Formally, this representation of $h_{BR}$ is
composed of a finite cover $I$ of $V$, and a mapping
$h'_{BR}:I\rightarrow A$ with the following properties:
\begin{itemize}
\item $I$ is a finite collection of subsets of $V$, and any value
  $v\in V$ is a member of some set $\alpha\in I$. This way, all values
  will be associated with some $a\in A$. Formally,
  $\cup_{\alpha\in I}\alpha = V$.
\item Since each $\alpha\in I$ will be associated with a particular
  $a\in A$, a potential conflicting assignment may arise for player
  types that simulataneously belong to two (or more) subsets in
  $I$. This conflict, however, can be made ineffectual if types within
  these intesections almost never appear. In other words, there are no
  significant intersections between subsets in $I$, where significance
  is with respect to the probability (measure) of values. Formally,
  $\forall \alpha_1,\alpha_2\in I, \mu(\alpha_1\cap\alpha_2)=0$
\item For those types that belong to only one $\alpha\in I$, there has
  to be a unique action we associate with them. Furthermore the action
  has to correspond to the one prescribed by $h_{BR}$. Formally,
  $\forall \alpha\in I,
  \lambda_1,\lambda_2\in\alpha\setminus\bigcup\limits_{\beta\in
    I\setminus\{\alpha\}}\beta\Rightarrow
  h_{BR}(\lambda_1)=h'_{BR}(\alpha)=h_{BR}(\lambda_2)$
\item Finally, we would like the cover $I$ to be as small as
  possible. So that two distinct subsets in $I$ only exist if the best
  response function $h_{BR}$ over them is not uniform. $\forall
  \alpha_1\neq\alpha_2\in
  I,\lambda_1\in\alpha_1\setminus\alpha_2,\lambda_2\in\alpha_2\setminus\alpha_1\land\lambda_1\neq\lambda_2\Rightarrow
  h_{BR}(\lambda_1)=h'_{BR}(\alpha_1)\neq
  h'_{BR}(\alpha_2)=h_{BR}(\lambda_2)$
\end{itemize}

To obtain such a family, we can formally index the cover $I$ by
actions, so that $|I|=|A|$, and define for each $a\in
A$. $\alpha_a=\{v\in V:\forall a'\in A\ u(v,a,m)\geq
u(v,a',m)\}$. Naturally $h'_{BR}(\alpha_a)=a$. Due to their
construction $\alpha_a$ represent the action distribution $m_{BR}$
engendered by $h_{BR}$:
$m_{BR}(a)=\mu(\alpha_a)=\mu(h_{BR}^{-1}(a)$. In fact, the functional
representation $h_{BR}:V\rightarrow A$ and the cover representation
$I$ (together with an appropriate $h'_{BR}$) are
equivalent. Furthermore, if $h^*$ is the equilibrium strategy then the
engendered action distribution $m^*$ is an equivalentin representation
for the equilibrium as well. This is easy to see, since for $m*$ the
best response is $h^*$ itself.

Now, in general it may not be trivial to calculate the collection
$I$. However, if $u(v,a,m)$ is analytical, the necessary calculations
can be done efficiently. In particular, if $u(v,a,m)$ is continuous in $v$
then all $\alpha_a$ are finite collections of connected
sets. Furthermore, if we assume that for each $a\in A$ the function
$u_{a,m}(v)$ is linear in $v\in V$, then the utility of the best
response is a piece-wise linear. If in addition $V=[0,1]$, then all
$\alpha_a$ are contiguous intervals\footnote{If
  $V\subset\mathbf{R}^n$, then $\alpha_a$ become polygons.}.

Given an opponent distribution $m\in\Delta(A)$, and the fact that
$u_{a,m}(v)$ are linear, the calculation of the best response function
$h_{BR}$ becomes efficient, since in the worst case scenario only
$|A|^2$ need to be computed. Furthermore, if the interval based
representation of the best response funciton is used, then the inverse
$h^{-1}_{BR}$ can be computed efficiently as
well. Figure~\ref{br_cals} shows a brute force algorithm for
$V=[0,1]$, to calculate the best response representations, including
the action distribution that it engenders. It is easy to see that the
algorithm can be extended for any dimentionality of $V=[0,1]^k$,
though naturally the number of points that need to be examined grows
exponentially with $k$. It is possible, however, given more specific
information about $u(v,a,m)$, to expedite and optimise the process of
the best response calculation. For instance, it is possible to borrow
several envelope calculation techniques from the area of
POMPDs~\cite{murphy2000}.

\begin{figure}[ht]
{\center 
\begin{tabular}{|l |}\hline \parbox{3.5 in} {
\begin{algorithmic}[1]
\REQUIRE\ \ \\
Set the set of intersection points $\Theta=\{0,1\}$
\FOR {$a_1\neq a_2\in A$}
\STATE $\theta_{a_1,a_2}$ s.t. $u(\theta_{a_1,a_2},a_1,m)=u(\theta_{a_1,a_2},a_2,m)$
\STATE $\Theta=\Theta\cup\{\theta_{a_1,a_2}\}$
\ENDFOR
\FOR {$\theta_{a_1,a_2}\in\Theta$}
\FOR {$a\in A\setminus\{a_1,a_2\}$}
\IF{$u(\theta_{a_1,a_2},a,m)\geq u(\theta_{a_1,a_2},a_1,m)$}
\STATE $\Theta=\Theta\setminus\{\theta_{a_1,a_2}\}$
\STATE break loop
\ENDIF
\ENDFOR
\STATE Sort $\Theta$ in an increasing order
\FOR{two consequtive $\theta_{a_1,a_2}$ and
  $\theta_{a_2,a_3}$ in $\Theta$}
\STATE associate interval $\alpha_{a_2}$ with $a_2\in A$
\STATE let for all $v\alpha_{a_2}$ $h_{BR}(v)=a_2$
\STATE let $m_{BR}(a_2)=\mu(\alpha_{a_2})$
\ENDFOR
\ENDFOR
\end{algorithmic}
} \\ \hline \end{tabular}
\\}
\caption{\label{br_cals} BR calculation for symmetric partial information games}
\end{figure}

The above procedure allows calculation of the best response
efficiently in all representation forms, and can be used in an
iterative fashion. In some cases, iterative best response may
converge, resulting in a symmetric equilibrium strategy. However, as
has been shown in~\cite{???}, for simultaneous auctions best response
iteration does not converge, and a more complex algorithm is required
to calculate an equilibrium strategy. In the following section we
show one such algorithm.

\section{Fictitious Play}\label{fp_descript}

Fictitious Play (FP) has been introduced by
Brown~\cite{brown_51,von_Neumann_brown_50} to solve normal form finite
games. In its symmetric form, FP dictates the following two-steps need
to be iterated until convergence:
\begin{itemize}
\item At every step $t$, given some opponent strategy $\sigma_t$,
  calculate the best response $\delta_t$ to that strategy
\item Merge $\sigma_t$ and $\delta_t$ into the new strategy
  $\sigma_{t+1}$
\end{itemize}
The merge in the second step is usually done so that the effects of
$\delta_t$ are diminished with time, and there are more than one way
to do so, which leads to several versions of FP (see
e.g.~\cite{fudenberg_levine_95}). In the standard FP, as it is applied
to normal form games, the merging of $\sigma_t$ and $\delta_t$ results
in a mixed strategy $\sigma_{t+1}$. However, due to the extreme
symmetry of our setup, at all stages of our FP version, the strategy
will remain pure. To acheive this, it will iterate between action
distributions that result from a strategy, rather than strategies
themselves. The detailed algorithm is given in Figure~\ref{fp_acg}.

\begin{figure}[ht]
%{\scriptsize
{\center
\begin{tabular}{|l |} \hline \parbox{3.2 in} {
\begin{algorithmic}[1]
\REQUIRE\ \ \\
Set iteration count $t=0$\\
Choose a starting point $m^0\in \Delta(A)$
\LOOP
\STATE Compute best response function:\ \  $h:V\rightarrow A$
\STATE Compute the best response {\em marginal} distribution:\\
\centerline{$m_{BR}(a)=\mu(h^{-1}(a))$}
\STATE Update beliefs:\\
\centerline{$m^{t+1}=\alpha(t)*m^t+(1-\alpha(t))*m_{BR}$}
\IF{ (Convergence precision reached) } 
\STATE {\bf return} $m^*=m^{t+1}$
\ENDIF
\STATE Set $t\leftarrow t+1$
\ENDLOOP
\end{algorithmic}
} \\ \hline \end{tabular} \\}
\caption{\label{fp_acg}FP for symmetric partical information games}
\end{figure}

The algorithm begins by initialising its beliefs, $m^0$, about the
action distribution that would occur in the equilibrium to an
arbitrary choice of actions. For example, players of all types may
select actions uniformly.  Notice that is does not matter what
strategy leads to this distribution, since the best response is
calculated based on action distribution, rather than the actual
strategy. The algorithm then enters a loop that continually computes a
best response and updates the beliefs. At iteration $t$, the best
response is computed (line 2) with respect to the currently held
beliefs about the equilibrium action distribution, $m^t$. Once
the response $h$ is obtained, its inherent action distribution is
calculated (line 3), and the beliefs of the next iteration
$m^{t+1}$ absorb it accordingly (line 4), with the standard
update rate of $\alpha(t)=\frac{t}{t+1}$. Finally, if the beliefs
indicate convergence (lines 5-6), the resulting distribution $m^*$
is returned. Since the returned distribution and the action
distribution of a best response to it are only marginally different,
we can treat $h_{BR}$ to $m^*$ as the symmteric equilibrium
strategy. 

Though relatively a simple extension of the best response iteration,
FP is extremely efficient and is widely applicable as an empirical
algorithm to solve symmetric partial information games that we
concentrate on. In particular, the algorithm only requires that an
efficient calculation of the best response and its inverse is
available. Furthermore, while best response iteration can easily fail,
in the case of simultaneous auctions, we show empirical FP convergence
results in Section~\ref{empirical_results}.

%\section{Analytical Results}\label{analytic_results}
%In this section we show that the structure of the envelope can be
%classified, leading to a set of polynomial systems of equations. Each
%system becomes solvable within a specific region of preference
%space. By bounding these regions we can break down the preference
%space into classes were a particular shape of equilibrium is
%obtained. Furthermore, the exact analytical expression can be obtained
%for the equilibrium parameterised by the preference.
%\newpage
\section{Analytical Characterisation of Equilibria}
\label{sec:char}\label{analytic_results}
%Under the private value model for selling a single object in a high bid auction, when bids and values are continuous, all equilibrium strategies are increasing in the bid~\ref{eqinshba00}. In fact, there is a unique symmetric equilibrium \commentv{need to find results on uniqueness of symmetric equilibria. Maskin in "Uniqueness of equilibrium in sealed high-bid
%auctions" claims "With a symmetric distribution of types, it
%is well known that there is only one symmetric equilibrium (Milgrom and Weber, 1982;
%Maskin and Riley, 1984)." Could not find the result for ind private value model in milgrom's paper.}
%%uniqueness in affiliated models is shown (krishn'a auction theory). what about private values?
%%It is well-known that in single auction equilibrium strategies, the bid increases in value\commentv{check + reference}. 
%Model with discrete bids was considered by in~\ref{discretefirstbid}.
%\commentv{list papers talking about sim auctions}
%Nobody has provided general characterization results for the setting with simultaneous auctions.
\begin{figure}
\begin{center}
\includegraphics[width=8cm]{img/envelope}
\end{center}
\caption{Utility lines for bids $B = \{b_1,b_2,b_3,b_4\}$ given bid distribution $h$. The best-response is highlighted.\label{fig:envelope}}
\end{figure}
For a given distribution $h$ of bids of any\footnote{We focus on anonymous settings and symmetric equilibria where the bid distribution of any agent is the same.} agent (henceforth, {\em bid distribution}), the utility that agent $i$ derives from submitting a bid $b_j$ is a linear function of the private type $\theta_i$
\begin{align*}
& u(\theta_i,b_j,h) = \theta_i \Pr[\text{win}\mid b_j,h] - E[\text{cost}\mid b_j,h]
\end{align*}
The probability of winning provides the slope and the expected cost provides the intercept.
For a given bid distribution $h$, Figure~\ref{fig:envelope} illustrates utility lines when an agent has four available. It is obvious from the picture that the best response of agent $i$ is given by a piecewise linear upper envelope formalized next.
%\begin{definition}
%\commentv{this will be removed and i'll talk about the upper envelope instead}
%A set of bids $B' = \{b_1, \ldots, b_{m'}\}$ and an increasing vector $a \in \R^{m'-1} \mid 0 \le a_1 \le \ldots \le a_{m'-1} \le 1$ define a {\em piecewise linear strategy}
%\begin{align*}
%& s(\theta_i) = b_{j} \quad \text{if } \theta_i \in [a_{j-1},a_{j}] \quad \forall 1 \le j\le m'
%\end{align*}
%with the convention $a_0 = 0$ and $a_{m'} = 1$. 
%\end{definition}
Let $B = (b_1, \ldots, b_m)$ denote the set of available bids ordered according to the increasing slope of their utility lines.
An upper envelope of utility lines for bids $B$ is a set of $m'$ intervals of these lines $[0,a_{1}],\ [a_{1},a_{2}],\ [a_{2},a_{3}],\ldots,\ [a_{m'-1},1]$ defined by $m'-1$ constants $0 < a_1 < a_2 < \cdots < a_{m'-1} < 1$. Denote by $b_{\sigma(j)}$ the bid that is the best-response on the interval $[a_j, a_{j+1}]$. We refer to the set of $m'$ such bids as $B' = \{b_{\sigma(1)}, \ldots, b_{\sigma(m')}\} \subseteq B$. Thus, an upper envelope and a best-response strategy are completely specified by a pair $(B',a)$. \commentv{reference Zinovi's characterization} Depending on the context, $(B',a)$ may refer to either the upper envelope or the best-response strategy.
In Figure~\ref{fig:envelope}, the best response is given by $B' = \{b_1,b_3,b_4\}$, and $a_1=x$, $a_2=y$. 
Next, we characterize a best-response pair $(B',a)$ algebraically.
\begin{lemma}
\label{lem:ue}
Given a bid distribution $h$ and possible bids $B = (b_1, \ldots, b_m)$ ordered according to the increasing slope of their utility lines, the {\em best response} is an upper envelope $(B',a)$ such that
\begin{align}
& u(a_{j},b_{\sigma(j)},h) = u(a_{j},b_{\sigma(j+1)},h) \quad \forall\ 1 \le j \le m'-1 \label{eq:ut}\\
& 0 < a_1 < \ldots < a_{m'-1} < 1 \label{eq:a}\\
& u(0,b_{\sigma(1)},h) \ge u(0,b_k,h) \quad \forall\   k < \sigma(1) \label{eq:utineq1}\\
& u(a_{j},b_{\sigma(j)},h) \ge u(a_{j},b_k,h) \quad \forall\ 1 \le j \le m' \quad \sigma(j) < k < \sigma(j+1) \label{eq:utineq2}
\end{align}
where $B' \subseteq B$, $m' = |B'|$, $b_{\sigma(j)}$ is the $j$th bid in $B'$,  $\sigma(m'+1) = m+1$, $a_0 = 0$, and $a_{m'} = 1$.
\end{lemma}
\begin{proof}
The set of bids $B'$ specifies the utility lines that provide intervals for an envelope (not necessarily an upper envelope). 
Consecutive intervals are connected at the point where the corresponding utility lines intersect. The end points of intervals are given by simultaneous equations~\ref{eq:ut}. As the slopes of the intervals are increasing and $a_1 < a_2 < \cdots < a_{m'-1}$, we get an envelope defined by $B'$. Note that not all $B'$ support an envelope (e.g., $\{b_1,b_4\}$ does but $\{b_1,b_2,b_4\}$ does not), and Equations~\ref{eq:ut} and~\ref{eq:a} have a solution only for the subsets $B'$ that do. Equations~\ref{eq:utineq1} and~\ref{eq:utineq2} make sure that the envelope is an upper envelope. %Specifically, Equations~\ref{eq:utineq2} check that no utility line with slopes between two
In more detail, Equations~\ref{eq:utineq1} and~\ref{eq:utineq2} imply that at each point $a_j$, the values of all utility lines are below $u(a_{j},b_{\sigma(j)},h)$, which with linearity guarantees that the utility lines of the bids $B \setminus B'$ are below the envelope $(B',a)$.
\end{proof}

%The best response on the interval $[a_{j-1}, a_{j}]$ for $1 \le j \le m'$ is given by the utility line $u(\cdot,b_{\sigma(j)},h)$ for bid $b_{\sigma(j)} \in B'$.

%In auctions, only some information from the bid distribution is relevant to an agent's utility. Specifically, only the highest bid in each auction and the number of agents placing that bid (for tie-breaking) affects an agent's utility. For bid distributions resulting from symmetric equilibria, this information is contained in the equilibrium distribution of bids of any agent and the total number of agents. 
%A strategy is a symmetric equilibrium if and only if it is the best response to the bid distribution resulting from the other bidders playing this strategy. 
Equilibrium bids of agent $i$ are the best response to the bids of the other agents. By Lemma~\ref{lem:ue}, we know that a best-response takes the form of a piecewise linear upper envelope $(B',a)$. The strategy $(B',a)$ constitutes a symmetric equilibrium when it is the best response to the bid distribution it generates as stated in the following observation.\commentv{call this a theorem?}
\begin{observation}
\label{cor:symeq}
A symmetric equilibrium is given by a pair $(B',a)$ satisfying Equations~\ref{eq:ut}-\ref{eq:utineq2} for the bid distribution
\begin{align}
& h(b_{\sigma(j)};a) = F(a_j)-F(a_{j-1}) \quad \forall\ 1 \le j \le |B'|\label{eq:pdf}\\
& h(b_j;a) = 0 \quad \forall b_j \notin B'\label{eq:pdf2}
%& h(b;a) = \sum_{b' \in B' \mid b' \le b} h(b';a)\label{eq:cdf}
\end{align}
%As the strategy is the best response, it has the form described in Definition~\ref{def:ue}: i.e., it is given by a set of bids $B'$ ordered according to $\sigma$ and constants $a$. In any such strategy, the bid $b_{\sigma(j)} \in B'$ is played only by the types $\theta_i \in [a_j, a_{j-1}]$; i.e., with the probability $F(a_j)-F(a_{j-1})$. A piecewise linear strategy is a symmetric equilibrium if is the best response to the price distribution it induces.
\end{observation}
%The price distribution is defined by the upper-envelope strategy, which in turn is the best response to this price distribution. 
Observation~\ref{cor:symeq} tells us that finding equilibrium is equivalent to finding a set of bids and corresponding parameters that satisfy Equations~\ref{eq:ut}-\ref{eq:cdf}. 
A direct way of searching for an equilibrium is for each possible subset of bids $B' \subseteq B$ to check whether there exist parameters satisfying these equations. 
%One way to search for an equilibrium is to pick an ordered set of bids $B'\subseteq B$ and solve Equations~\ref{eq:ut} where the distribution $G$ is a function of $a$. 
%The solution is valid only if $0 \le a_1 \le \ldots \le a_{|B'|} \le 1$. 
%Note, that the ordering of slopes of bids $B'$ under the price distribution defined by $a$ is the same as the original ordering of bids in $B'$ as $a$ defines an upper envelope where the bids appear in order.
The equations can be arbitrarily complex depending on the distribution of types and number of players. In the next section, we derive analytical results for 2 identical auctions with 2 possible bids per auction, 2 bidders, and a uniform distribution of types. 
%Even there analytical derivation is rather cumbersome. More general examples are hardly solvable analytically, justifying the computation approach we present in section~\ref{}.


\subsection{Two Identical Items, Two Bidders, Two Bids Per Auction, Uniform Distribution of Types}
We restrict attention to 2 auctions each selling an identical item and 2 bidders with types uniformly distribution between $0$ and $1$. The only bids that can be placed in either auction are $0$ and $1$. The set of possible joint bids is  $B = \{(0,0)\ (0,1)\ (1,0)\ (1,1)\}$. In our model, identical items are encoded by the equality $\alpha=\beta$. We assume that the highest bid is the same as the highest possible independent value of the item setting $\alpha=\beta=1$. The only remaining complementarity parameter is $\gamma$, which determines how much more or less an agent values having both items. 
%The only assumption we place of $\gamma$ is that of free disposal: $\gamma \ge 1$. 
We analytically derive equilibria as a function of $\gamma$. We only consider positive values of $\gamma$ which model any natural complementarity structure. Negative values of $\gamma$ mean that the agent receives negative utility when he wins both items. Free disposal condition is satisfied for $\gamma$ values of 1 and above, and the value of 2 corresponds to independent auctions.

Recall that a symmetric equilibrium is a best response to the distribution of bids it induces.
For the uniform distribution of types between $0$ and $1$, the bid distribution in Equation~\ref{eq:pdf} induced by a piecewise linear strategy $(B',a)$ becomes
\begin{align*}
& h(b_{\sigma(j)};a) = F(a_j)-F(a_{j-1}) =  a_j - a_{j-1}
\end{align*}
%For case of 2 players, we have $G(\cdot,a) = h(\cdot,a)$.


We make a few observations before searching for piecewise linear strategies that constitute symmetric equilibria.
The bids $(0,1)$ and $(1,0)$ must be played with the same probability in equilibrium. Acquiring either item is isolation has the same utility for the agent. Notice that if $(1,0)$ is played more often than $(0,1)$, then the probability that the second auction has the price of $0$ is higher and the best response is to bid $(0,1)$ more often. Therefore, in equilibrium, the probabilities of bidding $(1,0)$ and $(0,1)$ are the same, and these bids share the same utility line. Since the bids share the same utility line, the best response interval on which either of the bids is played is continuous. If these bids are played in an equilibrium on the interval $[a_1,a_2]$, then there is a continuum of equivalent equilibria where
\begin{align*}
& s(\theta_i) = (0,1) \text{ or } (1,0) \mid f(1,0) = f(0,1) = \frac{a_2-a_1}{2} && \text{if } \theta_i \in [a_1,a_2]
\end{align*}
%A simple equilibrium of this form is the one switching from $(1,0)$ to $(0,1)$ halfway between $a_1$ and $a_2$: i.e., setting the parameter $a_2 = a_1 + \frac{a_3-a_1}{2}$. For the sake of clarity, we focus on this particular equilibrium in our derivations and let $a_2$ be determined by $a_1$ and $a_3$. 
For convenience, since the probabilities of playing bids $(1,0)$ and $(0,1)$ are the same, we will only talk about the bid $(1,0)$.


The order of slopes of the bids is the same for all values of $\gamma$ and all bid distributions: $(0,0)$ has the lowest slope, $(1,0)$ is next, and $(1,1)$ has the highest slope. \commentv{show this} It is easy to show that the bid $(0,0)$ is part of the best response to any bid distribution and thus, is played with a positive probability in any equilibrium. However, there are no equilibria with $(0,0)$ being the only bid in the support. These  observations imply that the possible sets of equilibrium bids are $\{(0,0)\ (1,0)\}$, $\{(0,0)\ (1,1)\}$, and the set of all bids $\{(0,0)\ (1,0)\ (1,1)\}$.  
We derive equilibria for each of these sets.

Consider the set $B' = \{(0,0)\ (1,0)\}$ as an example. In the notation of Lemma~\ref{lem:ue}, $m' = |B'| = 2$, and we are looking for the parameter $0\le a_1 \le 1$ satisfying
%Since bid $(1,1)$ is not part of the set, the piecewise linear strategy must set $a_3=1$; and since $(0,0)$ and $(1,0)$ are part of $B'$, the strategy sets $0<a_1<1$. Parameters $a_2$ and $a_3$ are linked and $a_3=1$, we have $a_2 = a_1 + \frac{a_3-a_1}{2}$. The only degree of freedom is $a_1$ which by Lemma~\ref{lem:ue} for the set $B' = \{(0,0)\ (1,0)\}$ must satisfy
\begin{align*}
& u(a_1,(0,0),h(\cdot,a)) = u(a_1,(1,0),h(\cdot,a))\\
& u(1,(1,0),h(\cdot,a)) \ge u(1,(1,1),h(\cdot,a))
\end{align*}
The system has a solution only for $0<\gamma \le 2(2 - \sqrt{2})$. The solution is unique and is given by
\begin{align*}
& a_1 = \frac{-4 - \gamma + \sqrt{16\gamma + \gamma^2}}{-4 + 2\gamma}
\end{align*}
Details of the derivation appear in the appendix.

Carrying out a similar analysis, we derive equilibria for the other 2 sets of bids. Detailed derivations can be found in the appendix. There is a unique equilibrium for each value of $\gamma$. Equilibrium as a function of $\gamma$ is plotted in Figure~\ref{fig:eq}. The probability of playing each bid is plotted as a function of $\gamma$. Since bids $(0,1)$ and $(1,0)$ have the same probability, they are plotted as one line denoting the total probability. The vertical lines separate regions where the bids in equilibrium support (appearing at the top of each region) change.
\begin{figure}
\begin{center}
\includegraphics[width=\columnwidth]{img/eq}
\end{center}
\caption{Equilibrium probability of playing each bid for each value of $\gamma$.\label{fig:eq}}
\end{figure}

Equilibrium probabilities of each bid are continuous in $\gamma$. 
For low degrees of complementarity, bid $(1,1)$ is not played, bid $(0,0)$ decreases and $(1,0)$ increases. Starting from  $\gamma= 2(2 - \sqrt{2})$, the probability of playing $(0,0)$ increases while $(1,0)$ decreases rapidly. The bid $(1,0)$ is no longer played in equilibrium after $\gamma$ reaches $2$. This is when the probability of $(0,0)$ begins to decrease approaching $0$ as $\gamma$ increases. The probability of bid $(1,1)$ becomes non-zero at $\gamma= 2(2 - \sqrt{2})$ and monotonically increases approaching $1$ in the limit. The only bids played with positive probability for $\gamma \ge 2$ are $(0,0)$ and $(1,1)$, which is consistent with the observation that only equal-bid pairs are played for items that display complementarity~\cite{krishna}.

The value of $\gamma = 2$ corresponds to independent auctions and equilibrium can be found for each auction separately. The single auction equilibrium  with possible bids $0$ and $1$ can be easily derived: the unique equilibrium is to bid $0$ for the values below $.5$ and to bid $1$ for the values above $.5$. Combining individual equilibrium strategies, we get the equilibrium strategy: bid $(0,0)$ for the values below $.5$  and $(1,1)$ for the values above. Each of the two equilibrium bids has the probability of $.5$ as can be seen in Figure~\ref{fig:eq} for $\gamma=2$.


\commentv{anything general to say about uniqueness or continuity results?}




\subsection{General methodology}
\subsection{Significant Illustrating Example -- 2x2x2}

\section{Empirical Results}\label{empirical_results}
\subsection{Convergence of FP for substitutes}
\subsection{Convergence of FP for compliments}
\subsection{Correspondence of FP and Poly-Sys equilibrium}

\section{Conclusions}
\appendix
\section{Cost and Winning Probabilities}\label{cost_win_numeric}
As a part of the best response calculation or as a part of equilibrium
verification, it is necessary to calculate the exact utility of a
bid. In this section we will show how this is done in the symmetric
case, where we assume that all (or all but one players) undertake the
same strategy.

Let the bidding be between $I$ ($|I|=n$) bidders on $K$ auctions with
distribution $\mu$ over the common type space $V=[0,1]$.  Given that
players follow some strategy $h:V\rightarrow\mathbf{B}$, where
$\mathbf{B}=\prod\limits_{k\in K}B_k$ the space of complete bids,
which engenders a distribution $m$ over the space of complete bids
$\mathbf{B}$ of each of the players. We would like to calculate the
utility of a player that has bid $\mathbf{b}\in\mathbf{B}$, given that
the player has been assigned type $v\in V$. In other words we would
like to provide an explicit expression for $u(v,\mathbf{b},m)$.

We will begin by calculating the probability that the player wins a
particular subset $\eta\subset K$ of auctions. For a given complete
bid $\mathbf{b}\in\mathbf{B}$ we will denote by
$\mathbf{b}_\eta=(b_k)_{k\in\eta}$ and correspondingly
$\mathbf{b}_{-\eta}=(b_k)_{k\in K\setminus\eta}$. For any two complete
bids $\bar{\mathbf{b}}$ and $\mathbf{b}$ we will take the binary
relationships to be element-wise. For example
$\bar{\mathbf{b}}_\eta>\mathbf{b}$ means that for all $k\in\eta$ holds
that $\bar{\mathbf{b}}_k>\mathbf{b}_k$, however it does not limit the
relationship between $\bar{\mathbf{b}}_{-\eta}$ and
$\mathbf{b}_{-\eta}$. Given this notation, the probability in question
is given by:

%$$
%P_B(\mathbf{b},\eta)=\sum\limits_{\bar{\mathbf{b}}....
%$$


 ....  Let the
bidding game be defined by the tuple $<I,V,\mathbf{B},\mu,u>$. Let
$\mathbf{b}$
\subsection{}\label{win_2x2x2}
\subsection{}\label{cost_2x2x2}

\input{appendix.tex}

\bibliographystyle{plain}
\bibliography{motivation_refs,caps_refs}
\end{document}



